package com.mdnote.practice.linked_list;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/10/13
 * @description 25. K 个一组翻转链表
 */
public class LeetCode25 {


    public static void main(String[] args) {
        LeetCode25 leetCode25 = new LeetCode25();

        ListNode root = new ListNode(5);
        root.next = new ListNode(6);
        root.next.next = new ListNode(7);
        root.next.next.next = new ListNode(8);
        root.next.next.next.next = new ListNode(9);
        root.next.next.next.next.next = new ListNode(10);
        root.next.next.next.next.next.next = new ListNode(11);
        root.next.next.next.next.next.next.next = new ListNode(12);
        ListNode listNode = leetCode25.reverseKGroup(root, 3);

//        ListNode listNode = leetCode25.reverse(root, root.next.next);
        ListNode cur = listNode;
        while (cur != null) {
            System.out.println(cur.val);
            cur = cur.next;
        }
    }

    // 基本思路为，反转kk个元素，head指向k + 1，继续递归
    public ListNode reverseKGroup(ListNode head, int k) {

        if (head == null ||k == 1) {
            return head;
        }

        // Terminator
        ListNode start = head, end = head;
        for (int i = 1; i <= k; i++) {
            if (end == null) {
                return head;
            }
            end = end.next;
        }

        ListNode nextHead = reverse(start, end);
        start.next = reverseKGroup(end, k);

        return nextHead;

    }

    // 从A反转到B
    private ListNode reverse(ListNode start, ListNode end) {

        ListNode cur = start, pre = null, next = null;
        while (cur != end) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

      public static class ListNode {
          int val;
          ListNode next;
          ListNode() {}
          ListNode(int val) { this.val = val; }
          ListNode(int val, ListNode next) { this.val = val; this.next = next; }
      }
}
